This invention relates to a self-organizing, wireless digital network. More specifically, it relates to a wireless network in which each node communicates directly only with neighboring nodes, the latter nodes relaying transmissions to more distant nodes. In one application of the invention, each node has a low-power transmitter and its neighboring nodes are only a few meters distant.
In one aspect the invention is directed at networks comprising a large number of nodes in relatively close proximity to each other. A typical application is an office environment in which a number of workstations and servers are linked in a local area network (LAN). Conventionally, these nodes are interconnected by cables, usually through a central hub. Installation of the cables is a material element of cost in these networks. Moreover, cabled networks are relatively inflexible in that a node usually cannot be moved from one location to another without installing a new cable. Furthermore, it is particularly expensive to install cables in completed structures, since they cannot be hidden from sight without "fishing" them through the spaces between walls or, in some cases, opening up the walls to gain access to the interiors.
The foregoing problems have been overcome in part by resort to wireless LANs, which replicate the conventional wired arrangements, e.g. ethernet and token ring, but without the use of cables. Each of the nodes includes a wireless transceiver which communicates with other nodes in the network by means of radio frequency signals. These networks eliminate the installation costs associated with wired networks and, furthermore, they provide substantially more flexibility with regard to location and relocation of the respective network nodes. Even so, the cost of these wireless networks is too high for some applications. For example, one might wish to use a network to interconnect large numbers of low-cost devices such as simple condition sensors and controllers and, in that case, the network interface of each node might well exceed the cost of the device. This problem would be even more acute in a home environment where the cost cannot be justified by possible savings that might be obtained in a commercial environment.
There are other arrangements which can be applied to wireless networks and, particularly, to networks that employ very short-range, and therefore low-cost transceivers. These are ad-hoc routing systems which generally fall under the category of "Link State Routing" and "Source Path Routing".
In Link State Routing each node maintains a routing table that specifies an "optimal" path toward each network destination. The meaning of "optimal" is generally interpreted to mean the shortest path, but may account for other factors such as load balancing.
When a node in a Link State Routing system is to transmit a message to a destination node, it first fetches from a routing table an entry for the specified destination. The routing table entry specifies which neighbor of the originating node should relay the message and the identification of that neighbor is installed in the message header as the recipient. The originating node then broadcasts the message. Of all the neighbors that receive the broadcast, only the specified recipient acts on the message, relaying the message in the same manner, according to the entry in its routing table corresponding to the destination node. This process continues until the message reaches the ultimate destination.
In Source Path Routing, the originating node enters the entire route of the message into the message header, identifying each node through which the message should be relayed in order to reach the destination node. If a receiving node is not the last named node in the message's source route, it simply relays the message to the next node on the route.
Both Link State Routing and Source Path Routing require that each node in the network keep a constant record of its neighboring nodes and, furthermore, that it broadcast any changes in its list of neighboring nodes. This requires that each node send periodic messages to each of its neighbors. All of these messages are generally undesirable since they consume power and system bandwidth. Moreover, they may facilitate the ability of eavesdroppers to ascertain system information, including the locations of individual nodes. These systems are also susceptible to breakdown resulting from errors in the transmission of neighboring-node information to the other nodes in the network.
It is therefore a principal object of the invention to provide a digital network having a relatively low cost per node. Another object of the invention is to provide a network that is completely flexible with regard to location, relocation and addition of network nodes. A further object is to provide a robust network that consumes relatively little power and bandwidth in establishing routing configuration and is also relatively immune to problems that cause failures of prior networks.